#include "stdafx.h"

#pragma once

unsigned int FactorialRec(unsigned int n)
{
	if(n > 1)
	{
		n *= FactorialRec(n - 1);
		return n;
	}
	else
	{
		return 1;
	}
}

unsigned int FactorialIte(unsigned int n)
{
	unsigned int ret = 1;

	while(n)
	{
		ret = ret * n--; 
	}

	return ret;
}

unsigned int PrintFactorial(unsigned int n)
{
	if(n > 1)
	{
		n *= PrintFactorial(n - 1);
		std::cout << n << " ";
		return n;
	}
	else
	{
		std::cout << "1 ";
		return 1;
	}
}

unsigned int FibonacciRec(unsigned int nth)
{
	if(nth <= 1)
	{
		return 1;
	}
	else
	{
		return FibonacciRec(nth - 1) + FibonacciRec(nth - 2);
	}
}

unsigned int FibonacciIte(unsigned int nth)
{
	unsigned int first = 0, second = 1, temp;

	while(nth--)
	{
		temp = first + second;
		first = second;
		second = temp;
	}

	return second;
}

unsigned int PrintFibonacci(unsigned int nth)
{
	unsigned int first = 0, second = 1, temp;

	while(nth--)
	{
		temp = first + second;
		first = second;
		second = temp;

		cout << first << endl;
	}

	cout << second << endl;
	return second;
}

int FastPower(int a, unsigned int n)
{
	if(n == 0)
	{
		return 1;
	}

	int ret = FastPower(a, n/2);

	if(n & 1)
	{
		return a * (ret * ret);
	}
	else
	{
		return (ret * ret);
	}
}

bool BinarySearchRec(int * arr, unsigned int lower, unsigned int upper, int target)
{
	if(!arr)
	{
		return false;
	}

	if(arr[lower] > arr[upper])
	{
		return false;
	}

	if(lower > upper)
	{
		return false;
	}

	unsigned int mid = lower + (upper - lower) / 2;

	if(target == arr[mid])
	{
		return true;
	}
	else if (target < arr[mid])
	{
		return BinarySearchRec(arr, lower, mid - 1, target);
	}
	else
	{
		return BinarySearchRec(arr, mid + 1, upper, target);
	}
}

bool BinarySearchIte(int * arr, unsigned int lower, unsigned int upper, int target)
{
	if(!arr)
	{
		return false;
	}

	while(1)
	{
		if(arr[lower] > arr[upper])
		{
			return false;
		}

		if(lower > upper)
		{
			return false;
		}

		unsigned int mid = (upper - lower) / 2 + lower;

		if(target == arr[mid])
		{
			return true;
		}
		else if(target < arr[mid])
		{
			upper = mid - 1;
		}
		else
		{
			lower = mid + 1;
		}
	}
}

void DoPermute(const char * inStr, char * outStr, char * used, unsigned int position)
{
	unsigned int len = strlen(inStr);

	if(position == len)
	{
		cout << outStr << endl;
		return;
	}

	for(int i = 0; i < len; ++i)
	{
		char c = inStr[i];

		if(used[c] == 1)
		{
			continue;
		}

		outStr[position] = c;

		used[c] = 1;
		DoPermute(inStr, outStr, used, position + 1);
		used[c] = 0;
	}
}

void Permute(const char * inStr)
{
	size_t len = strlen(inStr);

	char used[256] = { 0 };

	char * outStr = (char *)malloc(len + 1);
	outStr[len] = '\0';

	DoPermute(inStr, outStr, used, 0);
}